home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / SML⁄NJ 93+ / Documentation / examples / missionaries / search.sml < prev   
Encoding:
Text File  |  1995-12-30  |  847 b   |  44 lines  |  [TEXT/R*ch]
  1. (* state searching module *)
  2.  
  3. signature BUFFER =
  4. sig
  5.   type 'a buffer
  6.   exception EMPTY
  7.   val empty: 'a buffer
  8.   val get: 'a buffer -> 'a * 'a buffer
  9.   val put: 'a * 'a buffer -> 'a buffer
  10. end
  11.  
  12. signature STATE_SPACE =
  13. sig
  14.   type state
  15.   val goal: state -> bool
  16.   val moves: state -> state list
  17. end
  18.  
  19. signature SEARCH =
  20. sig
  21.   structure States: STATE_SPACE
  22.   val search: States.state -> unit
  23. end
  24.  
  25. functor Search(structure States: STATE_SPACE and Buffer: BUFFER): SEARCH =
  26. struct
  27.  
  28.   structure States = States
  29.  
  30.   open States Buffer
  31.  
  32.   fun search state = 
  33.       let fun try pending =
  34.           let val (current,pending) = get pending
  35.            in if goal current
  36.               then (print "found"; ())
  37.           else try(fold put (moves current) pending)
  38.           end
  39.        in try(put(state,empty))
  40.       handle EMPTY => (print "failed"; ())
  41.       end
  42.  
  43. end  (* Search *)
  44.